DROPS

Document

DOI: 10.4230/LIPIcs.FSTTCS.2011.115

Isomorphism testing of read-once functions and polynomials

Authors: Raghavendra Rao B .V. and Jayalal Sarma M. N.

Published in: LIPIcs, Volume 13, IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)

Abstract

In this paper, we study the isomorphism testing problem of formulas in the Boolean and arithmetic settings. We show that isomorphism testing of Boolean formulas in which a variable is read at most once (known as read-once formulas) is complete for log-space. In contrast, we observe that the problem becomes polynomial time equivalent to the graph isomorphism problem, when the input formulas can be represented as OR of two or more monotone read-once formulas. This classifies the complexity of the problem in terms of the number of reads, as read-3 formula isomorphism problem is hard for \co\NP. We address the polynomial isomorphism problem, a special case of polynomial equivalence problem which in turn is important from a cryptographic perspective[Patarin EUROCRYPT'96, and Kayal SODA'11]. As our main result, we propose a deterministic polynomial time canonization scheme for polynomials computed by constant-free read-once arithmetic formulas. In contrast, we show that when the arithmetic formula is allowed to read a variable twice, this problem is as hard as the graph isomorphism problem.

Cite as

Raghavendra Rao B .V. and Jayalal Sarma M. N.. Isomorphism testing of read-once functions and polynomials. In IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011). Leibniz International Proceedings in Informatics (LIPIcs), Volume 13, pp. 115-126, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2011)

Copy BibTex To Clipboard

@InProceedings{raob.v._et_al:LIPIcs.FSTTCS.2011.115,
  author =	{Rao B .V., Raghavendra and Sarma M. N., Jayalal},
  title =	{{Isomorphism testing of read-once functions and polynomials}},
  booktitle =	{IARCS Annual Conference on Foundations of Software Technology and Theoretical Computer Science (FSTTCS 2011)},
  pages =	{115--126},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-939897-34-7},
  ISSN =	{1868-8969},
  year =	{2011},
  volume =	{13},
  editor =	{Chakraborty, Supratik and Kumar, Amit},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops-dev.dagstuhl.de/entities/document/10.4230/LIPIcs.FSTTCS.2011.115},
  URN =		{urn:nbn:de:0030-drops-33202},
  doi =		{10.4230/LIPIcs.FSTTCS.2011.115},
  annote =	{Keywords: Isomorphism Problems, Computational Complexity, Read-once formulas, Read-once Polynomials}
}

Search Results

Documents authored by Rao B .V., Raghavendra

Isomorphism testing of read-once functions and polynomials

Abstract

Cite as

Thanks for your feedback!

Could not send message